package com.leetcode;

import com.leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 129. 求根节点到叶节点数字之和
 * 之前的写法
 * 1. 找到所有从根节点到叶子节点的路径
 * 2. 根据路径list从根节点到叶子算出来
 *
 * @author fy
 * @date 2022/4/24 22:17
 */
public class Solution129_1 {

    public int sumNumbers(TreeNode root) {
        List<List<Integer>> list = pathSum(root);
        if (list.isEmpty()) {
            return 0;
        }
        int sum = 0;
        for (List<Integer> item : list) {
            int itemSum = 0;
            for (int i = 0; i < item.size(); i++) {
                if (i == 0) {
                    itemSum += item.get(i);
                } else {
                    itemSum = itemSum * 10 + item.get(i);
                }
            }
            sum += itemSum;
        }
        return sum;
    }

    private List<List<Integer>> pathSum(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        if (isLeafNode(root)) {
            List<Integer> res = new ArrayList<>();
            res.add(root.val);
            list.add(res);
            return list;
        }
        List<List<Integer>> leftPath = pathSum(root.left);
        List<List<Integer>> rightPath = pathSum(root.right);
        leftPath.addAll(rightPath);
        if (!leftPath.isEmpty()) {
            for (List<Integer> item : leftPath) {
                //List<Integer> res = new ArrayList<>();
                //res.add(root.val);
                //res.addAll(item);
                //list.add(res);

                // 换一种写法
                item.add(0, root.val);
                list.add(item);
            }
        }
        return list;
    }

    private boolean isLeafNode(TreeNode node) {
        if (node == null) {
            return false;
        }
        return node.left == null && node.right == null;
    }

}
